// 1.双指针法：定义两个指针，两个指针行走的速度一样，从n开始向前向后寻找素数，当遇到的第一个素数时，输出该素数与原数的距离。
#include <stdio.h>
#include <math.h>

int is_prime(int n)
{
        if (n <= 1) return 0;
        for (int i = 2; i * i <= n; i++)
                if (n % i == 0)
                        return 0;
        return 1;
}

int main()
{
        int n;
        scanf("%d", &n);
        int p, q;
        int dis = 0;
        for (p = q = n; ;p--,q++)
        {
                if (is_prime(p)) {
                        dis = n - p;
                        break;
                } else if (is_prime(q)) {
                        dis = q - n;
                        break;
                }
        }
        printf("%d\n", dis);
        return 0;
}